package com.study.leetcode;

import java.util.Arrays;

public class Solution_322 {
    //假设 f(n) 代表要凑齐金额为 n 所要用的最少硬币数量，那么有：
    //f(n) = min(f(n - c1), f(n - c2), ... f(n - cn)) + 1
    //其中 c1 ~ cn 为硬币的所有面额。
    //再具体解释一下例如这个示例：
    //输入: coins = [1, 2, 5], amount = 11
    //输出: 3
    //解释: 11 = 5 + 5 + 1
    //题目求的值为 f(11)，第一次选择硬币时我们有三种选择。
    //假设我们取面额为 1 的硬币，那么接下来需要凑齐的总金额变为:
    //11 - 1 = 10，即 f(11) = f(10) + 1，这里的 +1 就是我们取出的面额为 1 的硬币。
    //同理，如果取面额为 2 或面额为 5 的硬币可以得到：
    //f(11) = f(9) + 1
    //f(11) = f(6) + 1
    //所以：f(11) = min(f(10), f(9), f(6)) + 1
    //=min(min(f(9),f(8),f(5))+1, min(f(8),f(7),f(4))+1, min(f(5),f(4),f(1))+1) + 1
    //

    /**
     * int[] res = new int[amount + 1];
     * Arrays.fill(res, 0);
     * int cost;
     * for (int i = 1; i < amount + 1; i++) {
     * cost = Integer.MAX_VALUE;
     * for (int coin : coins) {
     * if (i - coin >= 0) {
     * int re = res[i - coin];
     * cost = Math.min(cost, re + 1);
     * res[i] = cost;
     * }
     * }
     * }
     * return res[amount] == Integer.MAX_VALUE ? -1 : res[amount];
     */

    public static int coinChange(int[] coins, int amount) {
        //f(11) = f(9) + 1
        //f(11) = f(6) + 1
        //所以：f(11) = min(f(10), f(9), f(6)) + 1
        //=min(min(f(9),f(8),f(5))+1, min(f(8),f(7),f(4))+1, min(f(5),f(4),f(1))+1) + 1
        if(coins.length == 0) {
            return -1;
        }
        //声明一个amount+1长度的数组dp，代表各个价值的钱包，第0个钱包可以容纳的总价值为0，其它全部初始化为无穷大
        //dp[j]代表当钱包的总价值为j时，所需要的最少硬币的个数
        int[] dp = new int[amount+1];
        Arrays.fill(dp,1,dp.length,Integer.MAX_VALUE);
        //i代表可以使用的硬币索引，i=2代表只在第0个，第1个，第2个这三个硬币中选择硬币
        for (int i = 0; i < coins.length; i++) {
            for (int j = coins[i]; j <= amount; j++) {
                if(dp[j-coins[i]] != Integer.MAX_VALUE) {
                    dp[j] = Math.min(dp[j], dp[j-coins[i]]+1);
                }
            }
        }
        if(dp[amount] != Integer.MAX_VALUE) {
            return dp[amount];
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] coins = {5, 6, 7, 8};
        int i = coinChange(coins, 10);
        System.out.println("i = " + i);

    }
}
